package com.myown.structure.impl;

import com.myown.structure.TreeNode;

/**
 * 红黑树 <p>
 *
 * @author lincky
 * @version v1.0.0
 * @time 2017.02.28 13:23
 */
public class RedTree<E extends Comparable<E>> extends AbstactTree<E> {

    public RedTree() {
    }

    /**
     * 平衡而二叉树的插入操作 <p>
     *
     * 树结构调整原理：{@link #singleInsert(TreeNode, TreeNode)} <p>
     *
     * 平衡因子调整原理：{@link #balanceAfterInsertion(Node)}<p>
     *
     * @param node 插入节点的父节点
     * @param item 节点元素
     */
    @Override
    void insert(TreeNode<E> node, E item) {
        Node<E> newNode = new Node<E>(item);
        singleInsert(node, newNode);
        balanceAfterInsertion(newNode);
    }

    /**
     * 平衡二叉树的删除操作 <p>
     *
     * 树结构调整原理:{@link #singleDelete(TreeNode)} <p>
     *
     * 平衡因子调整原理:{@link #balanceAfterDeletion(Node)} <p>
     *
     * @param node 待删除节点
     */
    @Override
    void delete(TreeNode<E> node) {
        boolean originRed = ((Node) node).red;
        Node<E> balance = (Node<E>) singleDelete(node);
        if (balance != null && !red(balance)) {
            balanceAfterDeletion(balance);
        }
    }

    /**
     * 左孩子时调整原理（自下向上回溯）： <p>
     *
     * 1.叔叔为红色：父亲和叔叔置黑色，祖父置红色,并回溯两辈 <p>
     *
     * 2.叔叔为黑色，自己为右孩子：自己左旋，回溯一辈 <p>
     *
     * 3.叔叔为红色，自己为左孩子：父亲置黑色，祖父置红色，父亲右旋 <p>
     *
     * 时间复杂度：O(lgn) <p>
     *
     * @param node 插入节点
     */
    private void balanceAfterInsertion(Node<E> node) {
        Node<E> p, pp;
        while ((p = (Node<E>) node.parent) != null && p.red) {
            pp = (Node<E>) p.parent();
            if (p.isLeft()) {
                Node<E> ppr = (Node<E>) pp.right();
                if (ppr != null && ppr.red) {
                    setBlack(p);
                    setRed(pp);
                    setBlack(ppr);
                    node = pp;
                    continue;
                }
                if (node.isRight()) {
                    leftRotate(p);
                    Node<E> temp;
                    temp = node;
                    node = p;
                    p = temp;
                }
                setBlack(p);
                setRed(pp);
                rightRotate(pp);
            } else {
                Node<E> ppl = (Node<E>) pp.left();
                if (ppl != null && ppl.red) {
                    setBlack(p);
                    setRed(pp);
                    setBlack(ppl);
                    node = pp;
                    continue;
                }
                if (node == p.left()) {
                    rightRotate(p);
                    Node<E> temp;
                    temp = node;
                    node = p;
                    p = temp;
                }
                setBlack(p);
                setRed(pp);
                leftRotate(pp);
            }
        }
        setBlack(root);
    }

    /**
     * 删除修复 <p>
     *
     * 左孩子时修复原理： <p>
     *
     * 1.兄弟为红色
     * 2.兄弟为黑色，且其两个孩子为黑色
     * 3.兄弟为黑色，且其左孩子为红色，右孩子为黑色
     * 4.兄弟为黑色，且其右孩子为红色
     *
     * @param node 取代节点
     */
    private void balanceAfterDeletion(Node<E> node) {
        Node<E> brother;
        Node<E> parent = (Node<E>) node.parent;
        while ((node == null || !node.red) && node != root) {
            if (node.isLeft()) {
                brother = (Node<E>) parent.right();
                if (red(brother)) {
                    // case 1
                    setBlack(brother);
                    setRed(parent);
                    leftRotate(parent);
                    brother = (Node<E>) parent.right();
                }
                if ((brother.left == null || !red(brother.left)) &&
                        (brother.right == null || !red(brother.right))) {
                    // case 2
                    setRed(brother);
                    node = parent;
                    parent = (Node<E>) node.parent;
                } else {
                    if (brother.right == null || !red(brother.right)) {
                        // case 3
                        setBlack(brother.left);
                        setRed(brother);
                        rightRotate(brother);
                        brother = (Node<E>) parent.right();
                    }
                    // case 4
                    brother.red = red(parent);
                    setBlack(parent);
                    if (brother.right != null) {
                        setBlack(brother.right);
                    }
                    leftRotate(parent);
                    node = (Node<E>) root;
                }
            } else {
                brother = (Node<E>) parent.left();
                if (red(brother)) {
                    setBlack(brother);
                    setRed(parent);
                    rightRotate(parent);
                    brother = (Node<E>) parent.left();
                }
                if ((brother.left == null || !red(brother.left)) &&
                        (brother.right == null || !red(brother.right))) {
                    setRed(brother);
                    node = parent;
                    parent = (Node<E>) node.parent;
                } else {
                    if (brother.left == null || !red(brother.left)) {
                        setBlack(brother.right);
                        setRed(brother);
                        leftRotate(brother);
                        brother = (Node<E>) parent.left();
                    }
                    brother.red = red(parent);
                    setBlack(parent);
                    if (brother.left != null) {
                        setBlack(brother.left);
                    }
                    rightRotate(parent);
                    node = (Node<E>) root;
                }
            }
        }
        if (node != null) {
            setBlack(node);
        }
    }

    private void setBlack(Node<E> node) {
        node.red = false;
    }

    private void setRed(Node<E> node) {
        node.red = true;
    }

    private void setBlack(TreeNode<E> node) {
        setBlack((Node<E>) node);
    }

    private void setRed(TreeNode<E> node) {
        setRed((Node<E>) node);
    }

    private boolean red(Node<E> node) {
        return node.red;
    }

    private boolean red(TreeNode<E> node) {
        return red((Node<E>) node);
    }



    @Override
    void valid(TreeNode<E> node) {
        Node<E> nodeExp = (Node<E>) node;
        Node<E> parent = (Node<E>) nodeExp.parent;
        if (parent == null || parent.red) {
            assert !nodeExp.red;
        }
        if (nodeExp.left != null) {
            assert nodeExp.left.item().compareTo(nodeExp.item()) < 0;
            valid(nodeExp.left);
        }
        if (nodeExp.right != null) {
            assert nodeExp.right.item().compareTo(nodeExp.item()) > 0;
            valid(nodeExp.right);
        }
    }

    /**
     * 红黑树树内部链接节点 <p>
     *
     * 节点结构：颜色，左孩子，右孩子，父亲节点，元素 <p>
     *
     * 节点性质： <p>
     * 1.每个节点是红色或黑色 <p>
     * 2.根节点是黑色 <p>
     * 3.叶结点是黑色 <p>
     * 4.红色节点子节点是黑色 <p>
     * 5.各个节点路径上拥有相同数目的黑色节点 <p>
     *
     * @param <E> 存储数据类型
     */
    static class Node<E extends Comparable<E>> extends AbstactTree.Node<E> {
        boolean red;

        Node(E item, boolean red) {
            super(item);
            this.red = red;
        }

        /**
         * red node
         * @param item 元素
         */
        Node(E item) {
            super(item);
            red = true;
        }
    }
}
